<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
          "http://www.w3.org/TR/html4/loose.dtd">

<html lang="en">

<head>
  <meta http-equiv="Content-Type"
        content="text/html; charset=utf-8">
  <meta http-equiv="Content-Style-Type"
        content="text/css">
  <meta http-equiv="Content-Script-Type"
        content="text/javascript">
  <meta name="description"
        content="FreeType Glyph Conventions - FreeType Outlines">
  <meta name="Author"
        content="David Turner">

  <link rel="icon"
        href="../image/favicon_-90.ico">
  <link rel="shortcut icon"
        href="../image/favicon_-90.ico">
  <link rel="stylesheet"
        type="text/css"
        href="../css/freetype2_-90.css">

  <script type="text/javascript"
          src="../../../js/freetype2.js">
  </script>

  <title>FreeType Glyph Conventions | FreeType Outlines</title>
</head>


<body>

<div id="top"
     class="bar">
  <h1><a href="http://freetype.org/index.html">FreeType</a> Glyph
    Conventions&nbsp;/&nbsp;VI</h1>
</div>


<div id="wrapper">

<div class="colmask leftmenu">
  <div class="colright">
    <div class="col1wrap">
      <div class="col1">


        <!-- ************************************************** -->

        <div id="freetype-outlines">
          <h2>VI. FreeType Outlines</h2>

          <p>The purpose of this section is to present the way
            FreeType manages vectorial outlines, as well as the most
            common operations that can be applied on them.</p>

          <h3 id="section-1">1. FreeType outline description and
            structure</h3>

          <h4>a. Outline curve decomposition</h4>

          <p>An outline is described as a series of closed contours in
            the 2D plane.  Each contour is made of a series of line
            segments and B&eacute;zier arcs.  Depending on the file
            format, these can be second-order or third-order
            polynomials.  The former are also called quadratic or
            conic arcs, and they are used in the TrueType format.  The
            latter are called cubic arcs and are mostly used in the
            PostScript Type&nbsp;1, CFF, and CFF2 formats.</p>

          <p>Each arc is described through a series of start, end, and
            control points.  Each point of the outline has a specific
            tag which indicates whether it is describes a line segment
            or an arc.  The tags can take the following values:</p>

          <table>
            <tr>
              <td valign="top">
                <p><code>FT_CURVE_TAG_ON</code></p>
              </td>
              <td valign="top">
                <p>Used when the point is &lsquo;on&rsquo; the curve.
                  This corresponds to start and end points of segments
                  and arcs.  The other tags specify what is called an
                  &lsquo;off&rsquo; point, i.e., a point which isn't
                  located on the contour itself, but serves as a
                  control point for a B&eacute;zier arc.</p>
              </td>
            </tr>
            <tr>
              <td valign="top">
                <p><code>FT_CURVE_TAG_CONIC</code></p>
              </td>
              <td valign="top">
                <p>Used for an &lsquo;off&rsquo; point used to control
                  a conic B&eacute;zier arc.</p>
              </td>
            </tr>
            <tr>
              <td valign="top">
                <p><code>FT_CURVE_TAG_CUBIC</code></p>
              </td>
              <td valign="top">
                <p>Used for an &lsquo;off&rsquo; point used to control
                  a cubic B&eacute;zier arc.</p>
              </td>
            </tr>
          </table>

          <p>Use the <code>FT_CURVE_TAG(tag)</code> macro to filter out
            other, internally used flags.

          <p>The following rules are applied to decompose the
            contour's points into segments and arcs:</p>

          <ul>
            <li>
              <p>Two successive &lsquo;on&rsquo; points indicate a
                line segment joining them.</p>
            </li>
            <li>
              <p>One conic &lsquo;off&rsquo; point between two
                &lsquo;on&rsquo; points indicates a conic
                B&eacute;zier arc, the &lsquo;off&rsquo; point being
                the control point, and the &lsquo;on&rsquo; ones the
                start and end points.</p>
            </li>
            <li>
              <p>Two successive cubic &lsquo;off&rsquo; points between
                two &lsquo;on&rsquo; points indicate a cubic
                B&eacute;zier arc.  There must be exactly two cubic
                control points and two &lsquo;on&rsquo; points for
                each cubic arc (using a single cubic &lsquo;off&rsquo;
                point between two &lsquo;on&rsquo; points is
                forbidden, for example).</p>
            </li>
            <li>
              <p>Two successive conic &lsquo;off&rsquo; points force
                the rasterizer to create (during the scan-line
                conversion process exclusively) a virtual
                &lsquo;on&rsquo; point inbetween, at their exact
                middle.  This greatly facilitates the definition of
                successive conic B&eacute;zier arcs.  Moreover, it is
                the way outlines are described in the TrueType
                specification.</p>
            </li>
            <li>
              <p>The last point in a contour uses the first as an end
                point to create a closed contour.  For example, if the
                last two points of a contour were an &lsquo;on&rsquo;
                point followed by a conic &lsquo;off&rsquo; point, the
                first point in the contour would be used as final
                point to create an &lsquo;on&rsquo; &ndash;
                &lsquo;off&rsquo; &ndash; &lsquo;on&rsquo; sequence as
                described above.
            </li>
            <li>
              <p>The first point in a contour can be a conic
                &lsquo;off&rsquo; point itself; in that case, use the
                last point of the contour as the contour's starting
                point.  If the last point is a conic &lsquo;off&rsquo;
                point itself, start the contour with the virtual
                &lsquo;on&rsquo; point between the last and first
                point of the contour.
            </li>
          </ul>

          <p>Note that it is possible to mix conic and cubic arcs in a
            single contour, however, no font driver of FreeType
            produces such outlines currently.</p>

          <table class="vertical-space">
            <tr>
              <td>
                <img src="points_segment.png"
                     height="166"
                     width="221"
                     alt="segment example">
              </td>
              <td>
                <img src="points_conic.png"
                     height="183"
                     width="236"
                     alt="conic arc example">
              </td>
            </tr>
            <tr>
              <td>
                <img src="points_cubic.png"
                     height="162"
                     width="214"
                     alt="cubic arc example">
              </td>
              <td>
                <img src="points_conic2.png"
                     height="204"
                     width="225"
                     alt="cubic arc with virtual 'on' point">
              </td>
            </tr>
          </table>


          <h4>b. The <code>FT_Outline</code> descriptor</h4>

          <p>A FreeType outline is described through a simple
            structure
            called <a href="../reference/ft2-outline_processing.html#ft_outline"><code>FT_Outline</code></a>.
            Right now, the following fields are of interest:</p>

          <table class="vertical-space">
            <caption>
              <b><code>FT_Outline</code></b>
            </caption>
            <tbody>
              <tr>
                <td>
                  <code>n_points</code>
                </td>
                <td>
                  the number of points in the outline
                </td>
              </tr>
              <tr>
                <td>
                  <code>n_contours</code>
                </td>
                <td>
                  the number of contours in the outline
                </td>
              </tr>
              <tr>
                <td>
                  <code>points</code>
                </td>
                <td>
                  array of point coordinates
                </td>
              </tr>
              <tr>
                <td>
                  <code>contours</code>
                </td>
                <td>
                  array of contour end indices
                </td>
              </tr>
              <tr>
                <td>
                  <code>tags</code>
                </td>
                <td>
                  array of point flags
                </td>
              </tr>
            </tbody>
          </table>

          <p>Here, <code>points</code> is a pointer to an array of
            <a href="../reference/ft2-basic_types.html#ft_vector"><code>FT_Vector</code></a>
            records, used to store the vectorial coordinates of each
            outline point.  These are expressed in 1/64th of a pixel,
            which is also known as the <em>26.6&nbsp;fixed-point
            format</em>.</p>

          <p><code>contours</code> is an array of point indices to
            delimit contours in the outline.  For example, the first
            contour always starts at point&nbsp;0, and ends at
            point <code>contours[0]</code>.  The second contour starts
            at point <code>contours[0]+1</code> and ends at
            <code>contours[1]</code>, etc.  To traverse these points in a
            callback based manner,
            use <a href="../reference/ft2-outline_processing.html#ft_outline_decompose"><code>FT_Outline_Decompose</code></a>.</p>

          <p>Note that each contour is closed, and that the value
            of <code>n_points</code> should be equal
            to <code>contours[n_contours-1]+1</code> for a valid
            outline.</p>

          <p>Finally, <code>tags</code> is an array of bytes, used to
            store each outline point's tag.</p>


          <h3 id="section-2">2. Bounding and control box
            computations</h3>

          <p>As described earlier, a <em>bounding box</em> (also
            called <em>bbox</em>) is simply a rectangle that
            completely encloses the shape of a given outline.  The
            interesting case is the smallest bounding box possible,
            and in the following we subsume this under the term
            &lsquo;bounding box&rsquo;.  Because of the way arcs are
            defined, B&eacute;zier control points are not necessarily
            contained within an outline's (smallest) bounding box.</p>

          <p>Such a situation happens if one B&eacute;zier arc is, for
            example, the upper edge of an outline and an
            &lsquo;off&rsquo; point happens to be above the bbox.
            However, it is very rare in the case of character outlines
            because most font designers and creation tools always
            place &lsquo;on&rsquo; points at the extrema of each
            curved edges (as both the TrueType and PostScript
            specifications recommend), making hinting much easier.</p>

          <p>We thus define the <em>control box</em> (also
            called <em>cbox</em>) as the smallest possible rectangle
            that encloses all points of a given outline (including its
            &lsquo;off&rsquo; points).  Clearly, it always includes
            the bbox, and the two boxes are identical in most
            cases.</p>

          <p>Unlike the bbox, the cbox is much faster to compute.</p>

          <table class="vertical-space">
            <tr>
              <td>
                <img src="bbox1.png"
                     height="264"
                     width="228"
                     alt="a glyph with different bbox and cbox">
              </td>
              <td>
                <img src="bbox2.png"
                     height="229"
                     width="217"
                     alt="a glyph with identical bbox and cbox">
              </td>
            </tr>
          </table>

          <p>Control and bounding boxes can be computed automatically
            using the
            functions <a href="../reference/ft2-outline_processing.html#ft_outline_get_cbox"><code>FT_Outline_Get_CBox</code></a>
            and
            <a href="../reference/ft2-outline_processing.html#ft_outline_get_bbox"><code>FT_Outline_Get_BBox</code></a>.
            The former function is always very fast, while the
            latter <em>may</em> be slow in the case of
            &lsquo;outside&rsquo; control points (as it needs to find
            the extreme of conic and cubic arcs for
            &lsquo;perfect&rsquo; computations).  If this isn't the
            case, it is as fast as computing the control box.

          <p>Note also that even though most glyph outlines have equal
            cbox and bbox values to ease hinting, this is not
            necessarily the case if a transformation like rotation is
            applied to them.</p>


          <h3 id="section-3">3. Coordinates, scaling and
            grid-fitting</h3>

          <p>An outline point's vectorial coordinates are expressed in
            the 26.6&nbsp;format, i.e., in 1/64th of a pixel, hence the
            coordinates &lsquo;(1.0,-2.5)&rsquo; is stored as the
            integer pair &lsquo;(64,-160)&rsquo;, to name an
            example.</p>

          <p>After a glyph outline is scaled from the EM grid (in font
            units) to the current character dimensions, the hinter or
            grid-fitter is in charge of aligning important outline
            points (mainly edge delimiters) to the pixel grid.  Even
            though this process is much too complex to be described in
            a few lines, its purpose is mainly to round point
            positions while trying to preserve important properties
            like widths, stems, etc.</p>

          <p>The following operations can be used to round vectorial
            distances in the 26.6&nbsp;format to the grid:</p>

          <pre>
round( x )   == ( x + 32 ) &amp; -64
floor( x )   ==          x &amp; -64
ceiling( x ) == ( x + 63 ) &amp; -64</pre>

          <p>Once a glyph outline is grid-fitted or transformed, it
            often is interesting to compute the glyph image's pixel
            dimensions before rendering it.  To do so, one has to
            consider the following:</p>

          <p>The scan-line converter draws all the pixels
            whose <em>centers</em> fall inside the glyph shape.  In
            B/W rendering mode, it can also detect <em>drop-outs</em>,
            i.e., discontinuities coming from extremely thin shape
            fragments, in order to draw the &lsquo;missing&rsquo;
            pixels.  These new pixels are always located at a distance
            less than half of a pixel but it is not easy to predict
            where they will appear before rendering.</p>

          <p>This leads to the following computations:</p>

          <ul>
            <li>
              <p>compute the bbox</p>
            </li>
            <li>
              <p>grid-fit the bounding box with the following:</p>

              <pre>
xmin = floor( bbox.xMin )
xmax = ceiling( bbox.xMax )
ymin = floor( bbox.yMin )
ymax = ceiling( bbox.yMax )</pre>
            </li>
            <li>
              <p>return pixel dimensions, i.e.,</p>

              <pre>
width = (xmax - xmin)/64</pre>

              <p>and</p>

              <pre>
height = (ymax - ymin)/64</pre>
            </li>
          </ul>

          <p>By grid-fitting the bounding box, it is guaranteed that
            all the pixel centers that are to be drawn, <em>including
            those coming from drop-out control</em>, will
            be <em>within</em> the adjusted box.  Then the box's
            dimensions in pixels can be computed.</p>

          <p>Note also that, when translating a grid-fitted outline, one should
            <em>always use integer distances</em> to move an outline
            in the 2D plane.  Otherwise, glyph edges won't be aligned
            on the pixel grid anymore, and the hinter's work will be
            lost, producing <em>very low quality</em> bitmaps and
            pixmaps.</p>
        </div>

        <!-- ************************************************** -->

        <div class="updated">
          <p>Last update: 15-Jan-2021</p>
        </div>
      </div>
    </div>


    <!-- ************************************************** -->

    <div class="col2">
    </div>
  </div>
</div>


<!-- ************************************************** -->

<div id="TOC">
  <ul>
    <li class="funding">
      <form action="https://www.paypal.com/cgi-bin/webscr"
            method="post"
            target="_top">
        <input type="hidden"
               name="cmd"
               value="_s-xclick">
        <input type="hidden"
               name="hosted_button_id"
               value="SK827YKEALMT4">
        <input type="image"
               src="https://www.paypalobjects.com/en_US/i/btn/btn_donateCC_LG.gif"
               name="submit"
               alt="PayPal - The safer, easier way to pay online!">
      </form>
    </li>
    <li class="primary">
      <a href="http://freetype.org/index.html">Home</a>
    </li>
    <li class="primary">
      <a href="http://freetype.org/index.html#news">News</a>
    </li>
    <li class="primary">
      <a href="../index.html">Overview</a>
    </li>
    <li class="primary">
      <a href="../documentation.html">Documentation</a>
    </li>
    <li class="primary">
      <a href="http://freetype.org/developer.html">Development</a>
    </li>
    <li class="primary">
      <a href="http://freetype.org/contact.html"
         class="emphasis">Contact</a>
    </li>

    <li>
      &nbsp; <!-- separate primary from secondary entries -->
    </li>

    <li class="secondary">
      <a href="index.html">FreeType Glyph Conventions</a>
    </li>
    <li class="tertiary">
      <a href="glyphs-1.html">Basic Typographic Concepts</a>
    </li>
    <li class="tertiary">
      <a href="glyphs-2.html">Glyph Outlines</a>
    </li>
    <li class="tertiary">
      <a href="glyphs-3.html">Glyph Metrics</a>
    </li>
    <li class="tertiary">
      <a href="glyphs-4.html">Kerning</a>
    </li>
    <li class="tertiary">
      <a href="glyphs-5.html">Text Processing</a>
    </li>
    <li class="tertiary">
      <a href="glyphs-6.html" class="current">FreeType Outlines</a>
    </li>
    <li class="tertiary">
      <a href="glyphs-7.html">FreeType Bitmaps</a>
    </li>
  </ul>
</div>

</div> <!-- id="wrapper" -->

<div id="TOC-bottom">
</div>

</body>
</html>
